package com.captain.lc.动态规划;

/**
 * Des:
 *
 * @author XL
 * @Date 2021/10/20 10:29
 */
public class Offer_fib {
    static int mod = (int) 1e9 + 7;

    public int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fib(n - 1) + fib(n - 2);
    }

    /**
     * des:
     * 记忆化搜索
     *
     * @param n 目标值
     * @return {@link int }
     * @author captain
     * @date 2021/10/20 10:30
     */
    public int fib1(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        //dp[n] n时的数值
        int[] dp = new int[n + 1];
        //初始化值
        dp[0] = 0;
        dp[1] = 1;
        return fib1(n, dp);
    }

    public int fib1(int n, int[] dp) {
        //check data is exist
        //no exist
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (dp[n] == 0) {
            dp[n] = fib1(n - 1, dp) + fib1(n - 2, dp);
            dp[n] %= mod;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(new Offer_fib().fib1(45));
    }

}
